动态规划

Time Limit: 50 Sec Memory Limit: 128 MB

Description

一开始有n个数，一段区间的价值为这段区间相同的数的对数。
　　我们想把这n个数切成恰好k段区间。之后这n个数的价值为这k段区间的价值和。
　　我们想让最终这n个数的价值和尽可能少。
　　例如6个数1,1,2,2,3,3要切成3段，一个好方法是切成[1],[1,2],[2,3,3]，这样只有第三个区间有1的价值。因此这6个数的价值为1。

Input

第一行两个数n,k。
　　接下来一行n个数ai表示这n个数。

Output

一个数表示答案。

Sample Input

10 2
　　1 2 1 2 1 2 1 2 1 2

Sample Output

8

HINT

对于100%的数据1<=n<=100000,1<=k<=min(n,20),1<=ai<=n。

Solution

首先，暴力DP非常显然，f[i][j] 表示分了 i 段，当前做到第 j 个元素的最小值。

那么 f[i][j] = f[i - 1][k] + sum(k + 1, j)。我们打一个表，发现决策具有单调性。

但是显然，对于这道题，我们不能直接二分转移来的位置，由于sum并不好求。

所以我们可以考虑运用分治。执行k次。**Solve(l, r, L, R)**表示 j∈[l, r]，from∈[L, R]。

那么我们对于**[l, r]，考虑mid从[L, R]中的哪一个转移过来，假设是MidFrom**。

那么由于决策单调性，所以**[l, mid - 1]的决策点一定在[L, MidFrom]，[mid + 1, r]的决策点一定在[MidFrom, R]**。

移动两个指针now_l, now_r，维护sum即可。（复杂度我也不会证明呀QWQ）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 100005;
const int MOD = 1e9 + 7;
const s64 INF = 1e18;

int get()
{
    int res = 1, Q = 1; char c;
    while( (c = getchar()) < 48 || c > 57)
        if(c == '-') Q = -1;
    if(Q) res = c - 48;
    while( (c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res * Q;
}

int n, k;
int a[ONE], cnt[ONE];

s64 record[ONE], f[ONE], value;
int now_l, now_r;


void Move(int l, int r)
{
    while(now_r < r) cnt[a[++now_r]]++, value += cnt[a[now_r]];
    while(l < now_l) cnt[a[--now_l]]++, value += cnt[a[now_l]];
    while(now_r > r) value -= cnt[a[now_r]], cnt[a[now_r--]]--;
    while(l > now_l) value -= cnt[a[now_l]], cnt[a[now_l++]]--;
}

void Solve(int l, int r, int L, int R) //j=l~r, from = L~R
{
    if(l > r) return;
    int mid = l + r >> 1, MidFrom;
    s64 Ans = INF;
    for(int from = L; from <= R; from++)
    {
        if(from >= mid) break;
        Move(from + 1, mid);
        if(f[from] + value < Ans)
            Ans = f[from] + value, MidFrom = from;
    }
    record[mid] = Ans;
    Solve(l, mid - 1, L, MidFrom);
    Solve(mid + 1, r, MidFrom, R);
}

int main()
{
    n = get();    k = get();
    for(int i = 1; i <= n; i++)
        a[i] = get();

    for(int i = 0; i <= n; i++) f[i] = INF;
    f[0] = 0;
    for(int j = 1; j <= k; j++)
    {
        for(int i = 1; i <= n; i++) cnt[i] = -1;
        now_l = now_r = 1; value = 0, cnt[a[1]] = 0;
        Solve(1, n, 0, n - 1);
        for(int i = 1; i <= n; i++)
            f[i] = record[i], record[i] = 0;
    }
    printf("%lld", f[n]);
}